#include <stdio.h>
#include "QuickSort.h"


#define LENGTH 5

/*******************************************/
/* 购买卷数排序
/*******************************************/
int sortbooks(int* books)
{
	quicksort(books, 0, LENGTH);

	return (0);
}

/*******************************************/
/* 总书卷数计算
/*
/* @parame
/*    [in/   ] books: 书购买卷数列表
/* @return
/*    购买书总数
/*******************************************/
int sumfun(int* books)
{
	int i;
	int ret;

	ret = 0;
	for (i=0; i<LENGTH; i++)
	{
		ret += books[i];
	}

	return (ret);
}

/*******************************************/
/* check01
/* @parame
/*    [in/   ]x1~x5: 各卷图书册书
/*******************************************/
int check(int x1, int x2, int x3, int x4, int x5)
{
	if (x1 < 0)
	{
		return (1);
	}
	if (x2 < 0)
	{
		return (1);
	}
	if (x3 < 0)
	{
		return (1);
	}
	if (x4 < 0)
	{
		return (1);
	}
	if (x5 < 0)
	{
		return (1);
	}

	return (0);
}

/*******************************************/
/* 动态规划求解
/* @parame
/*    [in/   ] books: 已排序(min->max)的各卷书购买册书
/*    [  /out] c1~c2: 总额最小情况下的折扣方式
/*******************************************/
float dynamicprog(int* books, int* c1, int* c2, int* c3, int* c4, int* c5)
{
	// x1 ~ x5: 以打折方式购买书的卷数。例x5:购买5卷书(不同系列，组成打折套餐)的套数
	int i1;
	int x1,x2,x3,x4,x5;
	int num;
	float sum;
	float min;

	sum = 0;
	min = 0;

	// 总卷数
	num = sumfun(books);
	min = 8*num;

	// 动态规划
	// 购买册书已排序，books[0]为最少卷书的册数
	for(x5=0;x5<=books[0];x5++)
	{
		for(x4=0;x4<=(books[0]+books[1]);x4++)
		{
			for(x3=0;x3<=(books[0]+books[1]+books[2]);x3++)
			{
				for(x2=0;x2<=(books[0]+books[1]+books[2]+books[3]);x2++)
				{
					x1 = num - 2*x2 -3*x3 -4*x4 -5*x5;
					sum = x1*8 + 0.95*8*x2*2 + 0.9*8*x3*3 + 0.8*8*x4*4 + 0.75*8*x5*5;

					if (sum < min)
					{
						if(check(x1,x2,x3,x4,x5) == 0)
						{
							min = sum;
							*c1 = x1;
							*c2 = x2;
							*c3 = x3;
							*c4 = x4;
							*c5 = x5;
						}
					}
				}
			}
		}
	}

	return (min);
}

/*******************************************/
/* main
/*******************************************/
int main()
{
	int books[LENGTH];
	int x1, x2, x3, x4, x5;
	float ret;

	books[0] = 2;
	books[1] = 2;
	books[2] = 2;
	books[3] = 1;
	books[4] = 1;
	x1 = 0;
	x2 = 0;
	x3 = 0;
	x4 = 0;
	x5 = 0;

	// 各卷书价格相同，故无需考虑卷数与价格的对应关系
	// 排序
	sortbooks(books);
	// 动态规划求解
	ret = dynamicprog(books,&x1,&x2,&x3,&x4,&x5);

	printf("list: %d, %d, %d, %d, %d\r\n", x1, x2, x3, x4, x5);
	printf("sum: %.1f\r\n",ret);
}